/******************************************************************************
*  A Teaching GA					  Developed by Hal Stringer & Annie Wu, UCF
*  Version 2, January 18, 2004
*******************************************************************************/

import java.io.*;
import java.util.*;

public class Chromo
{
/*******************************************************************************
*                            INSTANCE VARIABLES                                *
*******************************************************************************/

   private Constant constant;
	public BitSet chromo;
	public int    chromoLength;
	
	public double rawFitness;
	public double sclFitness;
	public double proFitness;

   //Store simulation performance measures
   public double meanWaitingTimeAllLanes;
   public double meanTravelTimeAllLanes;
   public float  meanTravelTime[]  = new float[constant.MAX_NUMBER_OF_XML_ELEMENTS];
   public float  meanDensity[]     = new float[constant.MAX_NUMBER_OF_XML_ELEMENTS];
   public float  meanOccupancy[]   = new float[constant.MAX_NUMBER_OF_XML_ELEMENTS];
   public float  meanWaitingTime[] = new float[constant.MAX_NUMBER_OF_XML_ELEMENTS];
   public float  meanSpeed[]       = new float[constant.MAX_NUMBER_OF_XML_ELEMENTS];
   public float  vehiclesEntered[] = new float[constant.MAX_NUMBER_OF_XML_ELEMENTS];
   public float  vehiclesLeft[]    = new float[constant.MAX_NUMBER_OF_XML_ELEMENTS];
   public double  meanNumberOfVehicles[]               = new double[constant.MAX_NUMBER_OF_XML_ELEMENTS];
   public double  meanTrafficVolumeCarsPerHour[]       = new double[constant.MAX_NUMBER_OF_XML_ELEMENTS];
   public double  meanTrafficVolumeAtExitCarsPerHour[] = new double[constant.MAX_NUMBER_OF_XML_ELEMENTS];

/*******************************************************************************
*                            INSTANCE VARIABLES                                *
*******************************************************************************/

	protected static double randnum;

/*******************************************************************************
*                              CONSTRUCTORS                                    *
*******************************************************************************/

	public Chromo(){	
		
		chromoLength = Parameters.numGenes * Parameters.geneSize;
		chromo = new BitSet(Parameters.numGenes * Parameters.geneSize);
		
		switch(Parameters.encodingType)
		{
			case Parameters.BINARY_ENCODING: //Intentional Fall Through
			case Parameters.GRAY_ENCODING:
                //  Set gene values to a randum sequence of 1's and 0's 				
				for(int i = 0; i < chromoLength; i++){
					randnum = Search.r.nextDouble();
					if (randnum <= 0.5) chromo.set(i);
				}

			break;
			default:
				System.out.println("Invalid encoding type!");
				System.exit(1);
		}

		this.rawFitness = -1;   //  Fitness not yet evaluated
		this.sclFitness = -1;   //  Fitness not yet scaled
		this.proFitness = -1;   //  Fitness not yet proportionalized
      
      this.meanWaitingTimeAllLanes = -1;
      this.meanTravelTimeAllLanes  = -1;
      for (int i=0; i<constant.MAX_NUMBER_OF_XML_ELEMENTS; i++)
      {
         this.meanTravelTime[i]                     = -1;
         this.meanDensity[i]                        = -1;
         this.meanOccupancy[i]                      = -1;
         this.meanWaitingTime[i]                    = -1;
         this.meanSpeed[i]                          = -1;
         this.vehiclesEntered[i]                    = -1;
         this.vehiclesLeft[i]                       = -1;
         this.meanNumberOfVehicles[i]               = -1;
         this.meanTrafficVolumeCarsPerHour[i]       = -1;
         this.meanTrafficVolumeAtExitCarsPerHour[i] = -1;
       }//end for



	}

/*******************************************************************************
*                                MEMBER METHODS                                *
*******************************************************************************/

	//  Get Alpha Represenation of a Gene **************************************

	public String getGeneAlpha(int geneID){
		String alpha = "";
		BitSet gene = getGene(geneID);
		
		for(int i = Parameters.geneSize-1; i >= 0; i--) // Read the bits from MSB to LSB (left to right)
			alpha += (gene.get(i)) ? '1' : '0';
		
		return alpha;
	}
	
	public BitSet getGene(int geneID) {
		int start = geneID * Parameters.geneSize;
		int end   = start + Parameters.geneSize;
		
		return this.chromo.get(start, end);
	}

	//  Get Integer Value of a Gene (Positive or Negative, 2's Compliment) ****
	public int getIntGeneValue(int geneID){
		BitSet binary;
		int geneValue;
		boolean geneSign;
		
		geneValue = 0;

		if(Parameters.encodingType == Parameters.GRAY_ENCODING)
			binary = grayToBin(getGene(geneID), Parameters.geneSize);
		else
			binary = getGene(geneID);
	
		for(int i = binary.nextSetBit(0); i >= 0 && i < (Parameters.geneSize-1); i = binary.nextSetBit(i+1))
		{
			geneValue += 1<<i;
		}
		
		geneSign = binary.get(Parameters.geneSize-1);
		if (geneSign) geneValue = geneValue - (1<<(Parameters.geneSize-1));
		
		return (geneValue);
	}

	//  Get Integer Value of a Gene (Positive only) ****************************

	public int getPosIntGeneValue(int geneID){
		BitSet binary;
		int geneValue;
		
		geneValue = 0;

		if(Parameters.encodingType == Parameters.GRAY_ENCODING)
			binary = grayToBin(getGene(geneID), Parameters.geneSize);
		else
			binary = getGene(geneID);

		for(int i = binary.nextSetBit(0); i >= 0; i = binary.nextSetBit(i+1))
		{
			geneValue += 1<<i;
		}
		
		return geneValue;
	}

	//  Mutate a Chromosome Based on Mutation Type *****************************

	public void doMutation(){
		switch (Parameters.mutationType){

		case 1:     //  Replace with new random number
			
			for (int i = 0; i < chromoLength; i++){
				randnum = Search.r.nextDouble();
				if (randnum < Parameters.mutationRate){
                    chromo.flip(i);
				}
			}			
			break;

		default:
			System.out.println("ERROR - No mutation method selected");
		}
	}	

	//  Select a parent for crossover ******************************************
	public static int selectParent(Chromo[] member){

		double rWheel = 0;
		int j = 0;
		int k = 0;

		switch (Parameters.selectType){

		case 1:     // Proportional Selection
			randnum = Search.r.nextDouble();
			for (j=0; j<Parameters.popSize; j++){
				rWheel = rWheel + Search.member[j].proFitness;
				if (randnum < rWheel) return(j);
			}
			break;

		case 3:     // Random Selection
			randnum = Search.r.nextDouble();
			j = (int) (randnum * Parameters.popSize);
			return(j);

		case 2:     //  Tournament Selection
			double maxVal = 0;
            int position_num = 0;

            for (int i = 0; i < 4; i++) {
                int randpos = Search.r.nextInt(Parameters.popSize);
                if (member[randpos].proFitness > maxVal) {
                    maxVal = member[randpos].proFitness;
                    position_num = randpos;
                }
            }

            return position_num;

		default:
			System.out.println("ERROR - No selection method selected");
		}
	return(-1);
	}

	//  Produce a new child from two parents  **********************************
	public void mateParents(int pnum1, int pnum2, Chromo parent2, Chromo child1, Chromo child2){

		int xoverPoint1 = 0;
		int xoverPoint2 = chromoLength;

	    BitSet crossoverMask = new BitSet(chromoLength);
	    BitSet maskP1        = new BitSet(chromoLength);
	    BitSet maskP2        = new BitSet(chromoLength);
		
		switch (Parameters.xoverType){
	
			case 2:     //  Two Point Crossover
				xoverPoint2 = 1 + (int)(Search.r.nextDouble() * (chromoLength-1));
			
			case 1:     //  Single Point Crossover
	
				//  Select crossover point
				xoverPoint1 = 1 + (int)(Search.r.nextDouble() * (chromoLength-1));
				
				if(xoverPoint1 > xoverPoint2)
				{
					int swap = xoverPoint1;
					xoverPoint1 = xoverPoint2;
					xoverPoint2 = swap;
				}
				else if(xoverPoint1 == xoverPoint2) // set xoverPoint2 to the end and use 1 point crossover
				{
				    xoverPoint2 = chromoLength;	
				}

				// Build crossover mask
			    crossoverMask.set(xoverPoint1, xoverPoint2);
	
				break;
				
			case 3:     //  Uniform Crossover
				for(int i = 0; i < chromoLength; i++)
					if(Search.r.nextDouble() > 0.5) crossoverMask.set(i);
				
				break;
				
			default:
				System.out.println("ERROR - Bad crossover method selected");
		}
		    
		// Build parent masks
	    maskP1.or(this.chromo);    // Set equal to parent 1
	    maskP1.and(crossoverMask); // Mask it
	    maskP2.or(parent2.chromo); // Set equal to parent 2
	    maskP2.and(crossoverMask); // Mask it
	    
	    // Child1 crossover
	    child1.chromo.clear();
	    child1.chromo.or(this.chromo);       // Set equal to parent 1
	    child1.chromo.andNot(crossoverMask); // Apply inverse of mask
	    child1.chromo.or(maskP2);            // OR with masked parent 2
	    
	    // Child2 crossover
	    child2.chromo.clear();
	    child2.chromo.or(parent2.chromo);    // Set equal to parent 2
	    child2.chromo.andNot(crossoverMask); // Apply inverse of mask
	    child2.chromo.or(maskP1);            // OR with masked parent 1

		//  Set fitness values back to zero
		child1.rawFitness = -1;   //  Fitness not yet evaluated
		child1.sclFitness = -1;   //  Fitness not yet scaled
		child1.proFitness = -1;   //  Fitness not yet proportionalized
		child2.rawFitness = -1;   //  Fitness not yet evaluated
		child2.sclFitness = -1;   //  Fitness not yet scaled
		child2.proFitness = -1;   //  Fitness not yet proportionalized

      child1.meanWaitingTimeAllLanes = -1;
      child1.meanTravelTimeAllLanes  = -1;
      for (int i=0; i<constant.MAX_NUMBER_OF_XML_ELEMENTS; i++)
      {
         child1.meanTravelTime[i]                     = -1;
         child1.meanDensity[i]                        = -1;
         child1.meanOccupancy[i]                      = -1;
         child1.meanWaitingTime[i]                    = -1;
         child1.meanSpeed[i]                          = -1;
         child1.vehiclesEntered[i]                    = -1;
         child1.vehiclesLeft[i]                       = -1;
         child1.meanNumberOfVehicles[i]               = -1;
         child1.meanTrafficVolumeCarsPerHour[i]       = -1;
         child1.meanTrafficVolumeAtExitCarsPerHour[i] = -1;
       }//end for

      child2.meanWaitingTimeAllLanes = -1;
      child2.meanTravelTimeAllLanes  = -1;
      for (int i=0; i<constant.MAX_NUMBER_OF_XML_ELEMENTS; i++)
      {
         child2.meanTravelTime[i]                     = -1;
         child2.meanDensity[i]                        = -1;
         child2.meanOccupancy[i]                      = -1;
         child2.meanWaitingTime[i]                    = -1;
         child2.meanSpeed[i]                          = -1;
         child2.vehiclesEntered[i]                    = -1;
         child2.vehiclesLeft[i]                       = -1;
         child2.meanNumberOfVehicles[i]               = -1;
         child2.meanTrafficVolumeCarsPerHour[i]       = -1;
         child2.meanTrafficVolumeAtExitCarsPerHour[i] = -1;
       }//end for
	}
	
	//  Produce a new child from a single parent  ******************************
	public void mateParents(int pnum, Chromo child){

		//  Create child chromosome from parental material
		child.chromo.clear();
		child.chromo.or(this.chromo);

		//  Set fitness values back to zero
		child.rawFitness = -1;   //  Fitness not yet evaluated
		child.sclFitness = -1;   //  Fitness not yet scaled
		child.proFitness = -1;   //  Fitness not yet proportionalized

      child.meanWaitingTimeAllLanes = -1;
      child.meanTravelTimeAllLanes  = -1;
      for (int i=0; i<constant.MAX_NUMBER_OF_XML_ELEMENTS; i++)
      {
         child.meanTravelTime[i]                     = -1;
         child.meanDensity[i]                        = -1;
         child.meanOccupancy[i]                      = -1;
         child.meanWaitingTime[i]                    = -1;
         child.meanSpeed[i]                          = -1;
         child.vehiclesEntered[i]                    = -1;
         child.vehiclesLeft[i]                       = -1;
         child.meanNumberOfVehicles[i]               = -1;
         child.meanTrafficVolumeCarsPerHour[i]       = -1;
         child.meanTrafficVolumeAtExitCarsPerHour[i] = -1;
       }//end for

	}
	
	//  Sets this Chromo equal to the source  ***************************************
	public void setEqual (Chromo source){

		this.chromo.clear();
		this.chromo.or(source.chromo);

		this.rawFitness = source.rawFitness;
		this.sclFitness = source.sclFitness;
		this.proFitness = source.proFitness;


      this.meanWaitingTimeAllLanes = source.meanWaitingTimeAllLanes;
      this.meanTravelTimeAllLanes  = source.meanTravelTimeAllLanes;
      
      for (int i=0; i<constant.MAX_NUMBER_OF_XML_ELEMENTS; i++)
      {
         this.meanTravelTime[i]                     = source.meanTravelTime[i];
         this.meanDensity[i]                        = source.meanDensity[i];
         this.meanOccupancy[i]                      = source.meanOccupancy[i];
         this.meanWaitingTime[i]                    = source.meanWaitingTime[i];
         this.meanSpeed[i]                          = source.meanSpeed[i];
         this.vehiclesEntered[i]                    = source.vehiclesEntered[i];
         this.vehiclesLeft[i]                       = source.vehiclesLeft[i];
         this.meanNumberOfVehicles[i]               = source.meanNumberOfVehicles[i];
         this.meanTrafficVolumeCarsPerHour[i]       = source.meanTrafficVolumeCarsPerHour[i];
         this.meanTrafficVolumeAtExitCarsPerHour[i] = source.meanTrafficVolumeAtExitCarsPerHour[i];
      }
	}
	
	//convert given gray code to a binary representation.
	//Technique is similar to converting binary to gray,
	//but there is a main difference that seperates the two.
	public BitSet grayToBin(BitSet grayCode, int size)
	{
		BitSet binary = new BitSet(Parameters.geneSize);
		
		//assuming there is more than one bit in the string, do the following.
		//Step 1.  Write the most significant bit as the left-most bit in the new string
		//(it will be a 1).  I suppose add 0's to the left, to make size match.
		int index = 0;
		
		index = grayCode.length() - 1; // This is the index of the MSB
			
		if(index == -1) return binary; // All 0's, we're done
		
		binary.set(index);
			
		//XOR using the very last bit of the new Binary string and the next bit of the Remainder.
		for(int i = index-1; i >= 0; i--)
		{
			binary.set(i, (binary.get(i+1) != grayCode.get(i)) );
		}
		
		return binary;
	}
	
	public int BitToInt(Chromo source,int start,int end)
	{
        int res = 0, pow = 1;

        for ( int i = start ; i < end ; i++ , pow <<= 1 ) {
            if ( source.chromo.get( i ) ) {
                res |= pow;
            }
        }
        
        return res;

	}
}   // End of Chromo.java ******************************************************
